#include <iostream>
#include <vector>
#include <queue>
#include <unordered_set>
#include <algorithm> // 用于sort
using namespace std;

// 边权类，同时实现比较接口，用于排序
struct Edge {
    int from;
    int to;
    int weight;

    Edge(int f, int t, int w) : from(f), to(t), weight(w) {}

    // 重载小于运算符，用于优先队列的比较
    bool operator<(const Edge& other) const {
        return weight > other.weight; // 小顶堆
    }
};

// 工具类 - 并查集
class UnionFind {
private:
    vector<int> parent;

public:
    UnionFind(int n) {
        parent.resize(n);
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }

    void pair(int index1, int index2) {
        parent[find(index2)] = find(index1);
    }

    int find(int index) {
        if (parent[index] != index) {
            parent[index] = find(parent[index]);
        }
        return parent[index];
    }

    bool check(int index1, int index2) {
        return find(index1) == find(index2);
    }
};

// Prim算法求最小生成树
void prim(int n, const vector<vector<int>>& edges) {
    // 在Prim算法中使用邻接表存储图信息
    vector<vector<Edge>> wg(n);
    for (const auto& es : edges) {
        // 无向图转邻接表时两个方向都要添加
        Edge e1(es[0], es[1], es[2]);
        wg[e1.from].push_back(e1);
        Edge e2(es[1], es[0], es[2]);
        wg[e2.from].push_back(e2);
    }

    // 使用集合维护当前已加入最小生成树的顶点
    unordered_set<int> vts;

    // 使用优先队列快速获取当前最短的边权
    priority_queue<Edge> pq;

    // 最终生成的最小生成树用边权集表示
    vector<Edge> mst;

    // 初始化：从顶点0开始构建最小生成树
    vts.insert(0);
    for (const auto& e : wg[0]) {
        pq.push(e);
    }

    // 循环执行Prim算法：不断将当前符合条件的最短边加入MST
    while (vts.size() < n && !pq.empty()) {
        Edge minEdge = pq.top();
        pq.pop();

        // 若当前边的终点已经在MST中，该边无效，跳过
        if (vts.find(minEdge.to) != vts.end()) {
            continue;
        }

        // 否则，将这条边加入到MST中
        vts.insert(minEdge.to);
        mst.push_back(minEdge);

        // 往外扩展：将新顶点能访问到的边加入优先队列
        for (const auto& e : wg[minEdge.to]) {
            if (vts.find(e.to) == vts.end()) {
                pq.push(e);
            }
        }
    }

    // 完成，输出结果
    cout << "Prim:\n";
    if (vts.size() == n) {
        for (const auto& e : mst) {
            cout << e.from << "->" << e.to << "\n";
        }
    } else {
        cout << "当前图不连通！\n";
    }
}

// Kruskal算法求最小生成树
void kruskal(int n, const vector<vector<int>>& edges) {
    // 直接用边权集表示图，并按边权排序
    vector<Edge> sortedEdges;
    for (const auto& es : edges) {
        sortedEdges.emplace_back(es[0], es[1], es[2]);
    }
    sort(sortedEdges.begin(), sortedEdges.end());

    // 使用并查集快速判断两个顶点是否已经在同一棵子树当中
    UnionFind unionFind(n);

    // 最终生成的最小生成树用边权集表示
    vector<Edge> mst;

    // 循环执行Kruskal算法，不断将符合条件的最短边加入MST当中
    for (const auto& minEdge : sortedEdges) {
        // 如果最小生成树构建成功则退出循环
        if (mst.size() == n - 1) {
            break;
        }

        // 判断该条边两个顶点是否连通
        // 如果已经连通，不可再加入MST(否则会形成环)
        if (!unionFind.check(minEdge.from, minEdge.to)) {
            // 将新的边加入MST，同时在并查集标记两个顶点连通
            unionFind.pair(minEdge.from, minEdge.to);
            mst.push_back(minEdge);
        }
    }

    // 完成，输出结果
    cout << "Kruskal:\n";
    if (mst.size() == n - 1) {
        for (const auto& e : mst) {
            cout << e.from << "->" << e.to << "\n";
        }
    } else {
        cout << "当前图不连通！\n";
    }
}

int main() {
    int n = 6;
    vector<vector<int>> allEdges = {
        {0, 1, 34}, {0, 5, 19}, {0, 2, 46}, {2, 5, 25}, {2, 3, 17},
        {3, 4, 38}, {3, 5, 25}, {4, 5, 26}, {4, 1, 12}
    };

    prim(n, allEdges);
    kruskal(n, allEdges);

    return 0;
}